import java.awt.Color;
import java.util.ArrayList;
import java.util.Vector;
import java.io.Serializable;
import javax.swing.JTable;
import java.awt.Dimension;

/**
 * Graph represents both directed and undirected simple graphs.
 * Each undireted graph edge (i,j) is represented by two edges (i,j) and (j,i).
 * It is implemented as an adjacency matrix for the interface GraphADT<VA, EA>
 * with VertexAttr and EdgeAttr representing the vertex and edge.
 * Objects of Graph can be saved through serialization.
 *
 * @version 1.0
 * @author K.Vamsi Krishna
 */
public class Graph implements GraphADT<VertexAttr, EdgeAttr>, Serializable
{
	// specifies whether the graph is directed or undirected
	private boolean type;
	// specifies the number of vertices in the graph
	private int numVertices;
	// specifies the number of edges in the graph
	private int numEdges;
	// holds the VertexAttr objects for all vertices
	private ArrayList<VertexAttr> allVertices;
	// holds the EdgeAttr objects for all edges, is valid only if
	// corresponding entry in adjMatrix is 1
	private ArrayList<ArrayList<EdgeAttr>> allEdges;
	// represents the adjacency matrix of the graph with
	// 1 as the entry if edges exists else 0
	private ArrayList<ArrayList<Integer>> adjMatrix;

	/**
	 * Creates an empty Graph object of the "type" type.
	 * @param type Specifies the type of graph, valid values are Graph.DIRECTED and Graph.UNDIRECTED
	 */
	public Graph(boolean type)
	{
		int i;

		this.type = type;

		numVertices = 0;
		numEdges = 0;

		allVertices = new ArrayList<VertexAttr>(10);
		allEdges = new ArrayList<ArrayList<EdgeAttr>>(10);
		for(i=0;i<10;i++)
			allEdges.add(i,new ArrayList<EdgeAttr>(10));
		adjMatrix = new ArrayList<ArrayList<Integer>>(10);
		for(i=0;i<10;i++)
			adjMatrix.add(i,new ArrayList<Integer>(10));
	}

	/**
	 * Creates a copy of specified Graph object.Deep copying is done so that all
	 * the vertex objects and edge objects also get new copies.
	 */
	public Graph(Graph G)
	{
		int i, j;

		type = G.type;
		numVertices = G.numVertices;
		numEdges = G.numEdges;

		allVertices = (ArrayList<VertexAttr>)G.allVertices.clone();
		for(i=0;i<allVertices.size();i++)
			allVertices.set(i,new VertexAttr(G.allVertices.get(i)));

		adjMatrix = (ArrayList<ArrayList<Integer>>)G.adjMatrix.clone();
		for(i=0;i<adjMatrix.size();i++)
			adjMatrix.set(i,(ArrayList<Integer>)G.adjMatrix.get(i).clone());
		for(i=0;i<adjMatrix.size();i++)
			for(j=0;j<adjMatrix.get(i).size();j++)
				adjMatrix.get(i).set(j, new Integer(G.adjMatrix.get(i).get(j)));

		allEdges = (ArrayList<ArrayList<EdgeAttr>>)G.allEdges.clone();
		for(i=0;i<allEdges.size();i++)
			allEdges.set(i,(ArrayList<EdgeAttr>)G.allEdges.get(i).clone());
		for(i=0;i<allEdges.size();i++)
			for(j=0;j<allEdges.get(i).size();j++)
				if(adjMatrix.get(i).get(j).equals(new Integer(1)))
					allEdges.get(i).set(j, new EdgeAttr(G.allEdges.get(i).get(j)));
	}

	// public Graph(GraphADT G)
	// {
	//
	// }

	/**
	 * Returns the number of vertices in the graph.
	 */
	public int numVertices()
	{
		return this.numVertices;
	}

	/**
	 * Returns the number of edges in the graph.
	 */
	public int numEdges()
	{
		return this.numEdges;
	}

	/**
	 * Returns the type of the graph.
	 * @return True if the graph is directed, false if undirected.
	 */
	public boolean isDirected()
	{
		if(type == DIRECTED)
			return true;
		else
			return false;		
	}

	/**
	 * Adds an edge between vertex "from" and vertex "to" only when there is
	 * no existing edge between them. Self loops cannot be added. It makes a copy
	 * of ea and doesnot refer to it later.
	 * Raises IllegalVertexException if "from" or "to" denotes an invalid vertex.
	 * @param ea Refers to the EdgeAttr object to be attached with the new edge
	 */
	public void addEdge(int from, int to, EdgeAttr ea) throws IllegalVertexException
	{
		if( from >= 0 && from <= numVertices-1 && to >= 0 && to <= numVertices-1 && from != to)
		{
			if(!edgeExists(from, to))
			{
				numEdges++;
				if(type == DIRECTED)
				{
					adjMatrix.get(from).set(to,new Integer(1));
					allEdges.get(from).set(to, new EdgeAttr(ea));
				}
				else if(type == UNDIRECTED)
				{
					adjMatrix.get(from).set(to,new Integer(1));
					allEdges.get(from).set(to, new EdgeAttr(ea));

					adjMatrix.get(to).set(from,new Integer(1));
					allEdges.get(to).set(from, new EdgeAttr(ea));
				}
			}
		}
		else
			throw new IllegalVertexException("Specified vertex doesnot exist");
	}

	/**
	 * Removes an edge between vertex "from" and vertex "to" if there exists
	 * an edge between them.
	 * Raises IllegalVertexException if "from" or "to" denotes an invalid vertex.
	 * @return EdgeAttr object corresponding to the deleted edge or null when there was no edge
	 */
	public EdgeAttr removeEdge(int from, int to) throws IllegalVertexException
	{
		if( from >= 0 && from <= numVertices-1 && to >= 0 && to <= numVertices-1)
		{
			EdgeAttr ea = allEdges.get(from).get(to);

			if(edgeExists(from, to))
			{
				numEdges--;
				if(type == DIRECTED)
				{
					adjMatrix.get(from).set(to, new Integer(0));
					allEdges.get(from).set(to, null);
				}
				else if(type == UNDIRECTED)
				{
					adjMatrix.get(from).set(to, new Integer(0));
					allEdges.get(from).set(to, null);

					adjMatrix.get(to).set(from, new Integer(0));
					allEdges.get(to).set(from, null);
				}
			}
			return ea;
		}
		else
			throw new IllegalVertexException("Specified vertex doesnot exist");
	}

	/**
	 * Returns an edge between vertex "from" and vertex "to" if there exists
	 * an edge between them. The object returned is only a copy of the actual edge,
	 * so the changes made to it will not effect the actual edge.
	 * Raises IllegalVertexException if "from" or "to" denotes an invalid vertex.
	 * @return EdgeAttr object corresponding to the edge or null when there is no edge
	 */
	public EdgeAttr getEdge(int from, int to) throws IllegalVertexException
	{
		if( from >= 0 && from <= numVertices-1 && to >= 0 && to <= numVertices-1)
		{
			if(edgeExists(from, to))
				return new EdgeAttr(allEdges.get(from).get(to));
			else
				return null;
		}
		else
			throw new IllegalVertexException("Specified vertex doesnot exist");
	}

	/**
	 * Sets new EdgeAttr object for the edge between vertex "from" and vertex "to"
	 * if there exists an edge between them. It makes a copy of ea and doesnot
	 * refer to it later.
	 * Raises IllegalVertexException if "from" or "to" denotes an invalid vertex.
	 * @param ea Refers to the EdgeAttr object to be attached with the new edge
	 */
	public void setEdge(int from,int to, EdgeAttr ea) throws IllegalVertexException
	{
		if( from >= 0 && from <= numVertices-1 && to >= 0 && to <= numVertices-1)
		{
			if(edgeExists(from, to))
			{
				if(type == DIRECTED)
				{
					allEdges.get(from).set(to, new EdgeAttr(ea));
				}
				else if(type == UNDIRECTED)
				{
					allEdges.get(from).set(to, new EdgeAttr(ea));
					allEdges.get(to).set(from, new EdgeAttr(ea));
				}
			}
		}
		else
			throw new IllegalVertexException("Specified vertex doesnot exist");
	}

	/**
	 * Returns true if there exists an edge from "from" to "to".
	 * Raises IllegalVertexException if "from" or "to" denotes an invalid vertex.
	 */
	public boolean edgeExists(int from, int to) throws IllegalVertexException
	{
		if( from >= 0 && from <= numVertices-1 && to >= 0 && to <= numVertices-1)
			return adjMatrix.get(from).get(to).equals(new Integer(1));
		else
			throw new IllegalVertexException("Specified vertex doesnot exist");
	}

	/**
	 * Add an new vertex and attachs "va" with it. It makes a copy of va and
	 * doesnot refer to the passed object later.
	 * @param va Is a VertexAttr object to be attached to the new vertex.
	 * @return The vertex number of the newly created vertex.
	 */
	public int addVertex(VertexAttr va)
	{
		int i;

		numVertices++;

		allVertices.add(numVertices-1, new VertexAttr(va));

		// extend the adjMatrix and allEdge to accomodate new vertex
		// add new row and populate them with appropriate values
		allEdges.add(numVertices-1,new ArrayList<EdgeAttr>(numVertices));
		adjMatrix.add(numVertices-1,new ArrayList<Integer>(numVertices));
		for(i=0;i<numVertices;i++)
		{
			allEdges.get(numVertices-1).add(i,null);
			adjMatrix.get(numVertices-1).add(i,new Integer(0));
		}

		// add a new column, by adding new entry in all old rows
		for(i=0;i<numVertices-1;i++)
		{
			allEdges.get(i).add(numVertices-1,null);
			adjMatrix.get(i).add(numVertices-1,new Integer(0));
		}

		return numVertices-1;
	}

	/**
	 * Removes a vertex and hence all its corresponding edges.
	 * Removing a vertex automatically decrease the vetex number by 1 for all the
	 * vertices that followed the deleted vertex.
	 * Raises IllegalVertexException if v denotes an invalid vertex
	 * @return VertexAttr object of the deleted vetex
	 */
	public VertexAttr removeVertex(int v) throws IllegalVertexException
	{
		int r, c;
		if(v >= 0 && v <= numVertices-1)
		{
			numVertices--;

			VertexAttr va = allVertices.get(v);
			// delete the vetex
			allVertices.remove(v);
			// readjust the adjMatrix and allEdges
			// delete the column, by deleting corresponding entry in each row
			for(r=0;r<numVertices+1;r++)
			{
				adjMatrix.get(r).remove(v);
				allEdges.get(r).remove(v);
			}
			// delete the row
			adjMatrix.remove(v);
			allEdges.remove(v);

			// recompute the number of edges
			numEdges = 0;
			for(r = 0; r <= numVertices-1; r++)
				for(c = 0; c <= numVertices-1; c++)
					if(adjMatrix.get(r).get(c).equals(new Integer(1)))
						numEdges++;
			if(type == UNDIRECTED)
				numEdges = numEdges / 2;

			return va;
		}
		else
			throw new IllegalVertexException("Specified vertex doesnot exist");
	}

	/**
	 * Returns the VertexAttr object corresponding to the specified vertex.
	 * The object returned is only a copy of the actual vertex,
	 * so the changes made to it will not effect the actual vertex.
	 * Raises an IllegalVertexException if v denotes an invalid vertex.
	 */
	public VertexAttr getVertex(int v)	throws IllegalVertexException
	{
		if(v >= 0 && v <= numVertices-1)
		{
			return new VertexAttr(allVertices.get(v));
		}
		else
			throw new IllegalVertexException("Specified vertex doesnot exist");
	}

	/**
	 * Attaches a new VertexAttr objects to the specified vertex.  It makes a copy 
	 * of va and doesnot refer to the passed object later.
	 * Raises an IllegalVertexException if v denotes an invalid vertex.
	 */
	public void setVertex(int v, VertexAttr va) throws IllegalVertexException
	{
		if(v >= 0 && v <= numVertices-1)
			allVertices.set(v, new VertexAttr(va));
		else
			throw new IllegalVertexException("Specified vertex doesnot exist");
	}

	/**
	 * Returns the number of edges in to this vertex.
	 * Raises an IllegalVertexException if v denotes an invalid vertex.
	 * For undirected graphs both inDegree() and outDegree() return the
	 * same value denoting the degree of the vertex.
	 */
	public int inDegree(int v) throws IllegalVertexException
	{
		int in = 0;
		int r;

		if(v >= 0 && v <= numVertices-1)
		{
			for(r = 0; r <= numVertices-1; r++)
				if(edgeExists(r, v))
					in++;

			return in;
		}
		else
			throw new IllegalVertexException("Specified vertex doesnot exist");
	}

	/**
	 * Returns the number of edges out of this vertex.
	 * Raises an IllegalVertexException if v denotes an invalid vertex.
	 * For undirected graphs both inDegree() and outDegree() return the
	 * same value denoting the degree of the vertex.
	 */
	public int outDegree(int v) throws IllegalVertexException
	{
		int out = 0;
		int c;

		if(v >= 0 && v <= numVertices-1)
		{
			for(c = 0; c <= numVertices-1; c++)
				if(edgeExists(v, c))
					out++;

			return out;
		}
		else
			throw new IllegalVertexException("Specified vertex doesnot exist");
	}

	/**
	 * Give the list of all vertices adjacent to the given vertex.
	 * Raises an IllegalVertexException if v denotes an invalid vertex.
	 * @return Vector with Integer objects as elements.
	 */
	public Vector<Integer> getNeighbours(int v)	throws IllegalVertexException
	{
		Vector<Integer> nl = new Vector<Integer>();
		int c;

		if(v >= 0 && v <= numVertices-1)
		{
			for(c = 0; c <= numVertices-1; c++)
				if(edgeExists(v, c))
					nl.add(new Integer(c));

			return nl;
		}
		else
			throw new IllegalVertexException("Specified vertex doesnot exist");
	}

	/**
	 * Give the list of all vertices for which the given vertex is adjacent.
	 * Raises an IllegalVertexException if v denotes an invalid vertex.
	 * @return Vector with Integer objects as elements.
	 */
	public Vector<Integer> getNeighbourFor(int v) throws IllegalVertexException
	{
		Vector<Integer> nfl = new Vector<Integer>();
		int r;

		if(v >= 0 && v <= numVertices-1)
		{
			for(r = 0; r <= numVertices-1; r++)
				if(edgeExists(r, v))
					nfl.add(new Integer(r));
					
			return nfl;
		}
		else
			throw new IllegalVertexException("Specified vertex doesnot exist");
	}
	
	/**
	 * Removes all edges incident to or from vertex v.
	 * Throws IllegalVertexException if v is an invalid vertex.
	 */
	public void removeAllEdges(int v) throws IllegalVertexException
	{
		Vector<Integer> nl = getNeighbours(v);
		Vector<Integer> nfl = getNeighbourFor(v);
		int i;
		
		for(i = 0; i < nl.size(); i++)
			removeEdge(v, nl.get(i));
		if(type == DIRECTED)
		{
			for(i=0; i < nfl.size(); i++)
				removeEdge(nfl.get(i), v);
		}
	}
	
	/**
	 * Returns the adjaceny matrix (edge weights). If there is no edge its weight is
	 * loaded with 0. For undirected graphs the matrix is symmetric.
	 * @return A JTable object with rows and columns appropriately loaded.
	 */
	public JTable getAdjMatrix() throws IllegalVertexException
	{
		String colNames[] = new String[numVertices];
		Integer rowData[][] = new Integer[numVertices][numVertices];
		int i, j;

		for(i = 0; i < numVertices; i++)
			colNames[i] = new String(allVertices.get(i).getName());

		for(i = 0; i < numVertices; i++)
			for(j = 0; j < numVertices; j++)
			{
				if(edgeExists(i, j))
					rowData[i][j] = new Integer(getEdge(i,j).getWeight());
				else
					// if there is no edge between vertex i and j then its weight 
					// is regarded as 0.
					rowData[i][j] = new Integer(0);
			}

		return new JTable(rowData, colNames);
	}
	
	/**
	 * Sets new weights for all edges (new edges are created by this function
	 * if the weight becomes non-zero and existing edges are removed if the 
	 * weight becomes zero).
	 * For undirected graphs the matrix passed is expected to be symmetric,
	 * otherwise it may give unexpected results.
	 * @param adjMatrixTable is JTabel object loaded with new weights.
	 */
	public void setAdjMatrix(JTable adjMatrixTable) throws IllegalVertexException
	{
		int i, j;
		
		for(i = 0; i < numVertices; i++)
			for(j = 0; j < numVertices; j++)
			{
				if(((Integer)adjMatrixTable.getValueAt(i, j)) == 0)
				{
					if(edgeExists(i, j))
						removeEdge(i,j);
				}
				else
				{
					if(edgeExists(i,j))
					{
						EdgeAttr ea = getEdge(i, j);
						ea.setWeight(((Integer)adjMatrixTable.getValueAt(i,j)));
						setEdge(i, j, ea);
					}
					else
						addEdge(i, j, new EdgeAttr((Integer)adjMatrixTable.getValueAt(i,j)));
				}
			}
	}
	
	// The following functions are written for AdjMatrixDialog.java
	
	public String[] getColNames()
	{
		String colNames[] = new String[numVertices];
		int i, j;
		for(i = 0; i < numVertices; i++)
			colNames[i] = new String(allVertices.get(i).getName());
		return colNames;
	}
	
	public Object[][] getRowData()
	{
		Object rowData[][] = new Integer[numVertices][numVertices];
		int i, j;
		for(i = 0; i < numVertices; i++)
			for(j = 0; j < numVertices; j++)
			{
				if(adjMatrix.get(i).get(j).equals(new Integer(1)))
					rowData[i][j] = new Integer(allEdges.get(i).get(j).getWeight());
				else
					// if there is no edge between vertex i and j then its weight 
					// is regarded 0
					rowData[i][j] = new Integer(0);
			}
		return rowData;
	}

}